package com.algomypractice.linkedlist;

import com.sourcestruct.linearlist.SingleLinkedList;

/**
 * @author: ZhouBert
 * @date: 2019/6/6
 * @description: 有序链表合并（从小到大，保存节点）
 */
public class SingleLinkedMerge {

	public static void main(String[] args) {
		SingleLinkedList lastnode = new SingleLinkedList(9, null);
		SingleLinkedList nodea = new SingleLinkedList(7, lastnode);
		SingleLinkedList nodeb = new SingleLinkedList(5, nodea);
		SingleLinkedList nodec = new SingleLinkedList(3, nodeb);
		SingleLinkedList noded = new SingleLinkedList(1, nodec);
		System.out.println(noded);

		SingleLinkedList lastnode2 = new SingleLinkedList(10, null);
		SingleLinkedList nodea2 = new SingleLinkedList(8, lastnode2);
		SingleLinkedList nodeb2 = new SingleLinkedList(4, nodea2);
		SingleLinkedList nodec2 = new SingleLinkedList(3, nodeb2);
		SingleLinkedList noded2 = new SingleLinkedList(2, nodec2);
		System.out.println(noded2);

		//System.out.println(mergeByPoint(noded, noded2));//这个比较起来真是辣鸡代码
		//合并之后原来的也进行了排序，与 node 相同
		//System.out.println(mergeByPointBetter(noded, noded2));

		System.out.println(mergeByRecursion(noded, noded2));

	}

	/**
	 * 我的想法有点问题。——应该是当一个列表用完以后，直接将剩下的引用给 result 就可以了。看来指针还是理解不够深刻！
	 *
	 * @param list1
	 * @param list2
	 * @return
	 */
	public static SingleLinkedList mergeByPoint(SingleLinkedList list1, SingleLinkedList list2) {
		//由于我的例子没有边界条件，就先不管了

		//设置一个默认值，处理结束后删除
		SingleLinkedList result = new SingleLinkedList(-1);
		SingleLinkedList currresult = result;
		//1.定义连个指针
		SingleLinkedList curr1 = list1;
		SingleLinkedList curr2 = list2;
		//2.耗尽其中一方
		while (curr1 != null && curr2 != null) {
			if (curr1.getData() <= curr2.getData()) {
				//setNodeNext(result, curr1);
				currresult.setNext(new SingleLinkedList(curr1.getData()));
				curr1 = curr1.getNext();
			} else {
				currresult.setNext(new SingleLinkedList(curr2.getData()));
				curr2 = curr2.getNext();
			}
			currresult = currresult.getNext();
		}
		//3.1	如果是 curr1 耗尽
		if (curr1 == null) {
			while (curr2 != null) {
				currresult.setNext(new SingleLinkedList(curr2.getData()));
				curr2 = curr2.getNext();
				currresult = currresult.getNext();
			}
		}
		if (curr2 == null) {
			while (curr1 != null) {
				currresult.setNext(new SingleLinkedList(curr1.getData()));
				curr1 = curr1.getNext();
				currresult = currresult.getNext();
			}
		}
		return result;
	}

	/**
	 * @param list1
	 * @param list2
	 * @return 其实不是用于创建新数据，而是改变引用（避免前驱节点或者后继节点指向自己！）
	 */
	public static SingleLinkedList mergeByPointBetter(SingleLinkedList list1, SingleLinkedList list2) {
		//忽略边界条件

		SingleLinkedList p = list1;
		SingleLinkedList q = list2;
		//[记住头指针，用于返回]
		SingleLinkedList head;
		if (p.getData() <= q.getData()) {
			head = p;
			p=p.getNext();
		} else {
			head = q;
			q=q.getNext();
		}

		SingleLinkedList node = head;
		while (p != null && q != null) {
			if (p.getData() <= q.getData()) {
				node.setNext(p);
				p = p.getNext();
			} else {
				node.setNext(q);
				q = q.getNext();
			}
			node = node.getNext();
		}

		if (p == null) {
			node.setNext(q);
		} else {
			node.setNext(p);
		}
		return head;
	}

	/**
	 * 通过递归（感觉是利用巧劲）
	 * @param list1
	 * @param list2
	 * @return
	 */
	public static SingleLinkedList mergeByRecursion(SingleLinkedList list1, SingleLinkedList list2){
		//边界条件判断
		if(list1==null){
			return list2;
		}
		if (list2==null){
			return list1;
		}
		if (list1.getData()<list2.getData()){
			list1.setNext(mergeByRecursion(list1.getNext(), list2));
			return list1;
		}else {
			list2.setNext(mergeByRecursion(list1, list2.getNext()));
			return list2;
		}
	}


	private static void setNodeNext(SingleLinkedList result, SingleLinkedList curr) {
		result.setNext(new SingleLinkedList(curr.getData()));
		result = result.getNext();
	}
}
